Algoritma Graf Berbobot (Weighted Graph)
Memahami dua masalah terbesar dalam peta graf: Jarak Terpendek dan Rute Termurah.
Shortest Path (Jalur Terpendek)
Mencari rute paling cepat/pendek dari satu titik awal (Source) ke titik-titik lainnya. Digunakan dalam sistem navigasi seperti Google Maps.
Minimum Spanning Tree (MST)
Menghubungkan SELURUH node dalam graf sedemikian rupa sehingga total bobot seluruh jalurnya adalah yang paling minimal. Cocok untuk perancangan kabel listrik/fiber optik termurah.
Analogi Jaman Now
Shortest Path itu ibarat kamu mesen ojol dari rumah ke sekolah. Tukang ojol pasti nyari SATU jalur yang waktu tempuhnya paling cepat buat nganterin kamu doang.
MST (Minimum Spanning Tree) itu ibarat Pak RT mau ngaspal jalan kampung. Dia harus mastikan SEMUA rumah warga terhubung aspal, tapi dia mau ngabisin uang kas semen sesedikit mungkin. Pak RT nggak peduli dari rumah A ke Z jadi agak muter, yang penting total aspal se-kampung paling irit!
Algoritma Dijkstra (Shortest Path)
Mencari jarak terpendek dari kota awal ke semua kota lain menggunakan prinsip *Greedy*.
👩🏫 Secara Formal:
Algoritma Dijkstra bekerja dengan memelihara antrean prioritas (Priority Queue) dari simpul yang akan dikunjungi, diurutkan berdasarkan jarak terpendek saat ini dari titik asal (Source). Pada tiap langkah, ia mengambil titik terdekat yang belum "terkunci" (visited), lalu meregangkan (Relaxation) jarak ke semua tetangganya.
VISUALISASI RELAXATION DIJKSTRA
⚠️ Common Mistakes: Bobot Negatif (Negative Weights)
Siswa sering buta memakai Dijkstra pada SEMUA graf. Hati-hati! Dijkstra akan GAGAL / SALAH jika ada edge (jalan) dengan bobot angka negatif (misal jarak -5). Sifat Greedy Dijkstra berasumsi "sekali dikunjungi, jarak sudah pasti minimum", yang akan hancur jika jalan di depannya ternyata memberi diskon negatif. Untuk bobot negatif, WAJIB pakai algoritma Bellman-Ford!
Algoritma Kruskal (MST)
Membuat Minimum Spanning Tree dengan mengurutkan bobot termurah.
👩🏫 Secara Formal:
Algoritma Kruskal membentuk MST dengan sangat elegan: Pertama, kumpulkan SEMUA jalan (edge) lalu Urutkan (Sort) dari bobot terkecil ke terbesar. Kemudian, telusuri dari jalan termurah; jika jalan itu TIDAK membentuk siklus (lingkaran tertutup) dengan jalan yang sudah diambil, maka ambil! Ulangi sampai jumlah jalan yang diambil sama dengan V - 1 (Jumlah Kota - 1).
SIMULASI KRUSKAL (MEMILIH EDGE TERMURAH)
⚠️ Common Mistakes: Deteksi Siklus Lambat
Dalam Kruskal, syarat wajib untuk mengambil jalan adalah "TIDAK BOLEH membentuk siklus". Bagaimana cara komputer tahu ada siklus atau tidak? Kesalahan fatal pemula adalah menelusuri graf dengan BFS/DFS setiap kali akan mengecek siklus (sangat lambat!). Solusi profesionalnya adalah WAJIB menggunakan struktur data Disjoint Set Union (DSU) dengan optimasi Path Compression.
Evaluasi Graf Lanjut
Saatnya mengukur pemahaman Shortest Path dan Minimum Spanning Tree.
Kuis OSN Minggu 12
10 Butir soal tentang graf berbobot, algoritma pencarian jalur terpendek, dan spanning tree minimum.
Mulai Kuis Minggu 12